package ch5;
//普利姆算法
public class MiniSpanTree_PRIM {
    private class CloseEdge {       //内部类辅助记录从顶点集U到V-U的代价最小的边
        Object adjVex;
        int lowCoat;
        public CloseEdge (Object adjVex, int lowCoat) {
            this.adjVex = adjVex;
            this.lowCoat = lowCoat;
        }
    }

    //用普利姆算法从第u个顶点出发构造网G的最小生成树T，返回由生成树边组成的二维数组
    public Object[][] PRIM(MGraph G, Object u) throws Exception {
        Object[][] tree = new Object[G.getVexNum() - 1][2];
        int count = 0;
        CloseEdge[] closeEdges = new CloseEdge[G.getVexNum()];
        int k = G.locateVex(u);
        for (int j = 0; j < G.getVexNum(); j++)//辅助数组初始化
            if (j != k)
                closeEdges[j] = new CloseEdge(u, G.getArcs()[k][j]);
            closeEdges[k] = new CloseEdge(u,0);//初始，U={u}
        for (int i = 1;i<G.getVexNum();i++)//选择其余G.vexnum-1个顶点
            k = getMinMum(closeEdges);//求出T的下一个点：第k个顶点
        tree[count][0] = closeEdges[k].adjVex;//生成树的边放入数组中
        tree[count][1] = G.getVexs()[k];
        count++;
        closeEdges[k].lowCoat = 0;//第k个顶点并入U集
        for (int j=0;j<G.getVexNum();j++)//新顶点并入U后重新选择最小边
            if (G.getArcs()[k][j]<closeEdges[j].lowCoat)
                closeEdges[j] = new CloseEdge(G.getVex(k),G.getArcs()[k][j]);
            return tree;
    }
    private int getMinMum(CloseEdge[] closeEdges){//在closeEdge中选出lowCost最小且不为0的顶点
        int min = Integer.MAX_VALUE;
        int v = -1;
        for (int i =0;i<closeEdges.length;i++)
            if (closeEdges[i].lowCoat != 0 && closeEdges[i].lowCoat<min){
                min = closeEdges[i].lowCoat;
                v = i;
            }
        return v;
    }




}
